import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;


/*
 * @lc app=leetcode.cn id=39 lang=java
 *
 * [39] 组合总和
 */

// @lc code=start
class Solution {
    List<List<Integer>> res=new ArrayList<>();
    LinkedList<Integer> path=new LinkedList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates, target, 0,0);
        return res;   
    }
    public void dfs(int[] candidates,int target,int sum,int startIndex){
        if(sum>target){
            return;
        }
        if(sum==target){
            res.add(new LinkedList<>(path));
        }
        for(int i=startIndex;i<candidates.length&&sum+candidates[i]<=target;i++){
            sum+=candidates[i];
            path.add(candidates[i]);
            dfs(candidates, target, sum,i);//i则可以重复选择
            sum-=candidates[i];
            path.removeLast();
        }
    }
}
// @lc code=end

